// 将两个升序链表合并为一个新的 升序 链表并返回
// 新链表是通过拼接给定的两个链表的所有节点组成的
// 测试链接 : https://leetcode.cn/problems/merge-two-sorted-lists/

// 不要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 迭代
class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        if(list1 == nullptr || list2 == nullptr)
            return list1 ? list1 : list2;

        // 哨兵位头结点，解决链表题目常用的技巧
        ListNode* head = new ListNode(); 
        ListNode* tail = head;
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }

        tail->next = cur1 ? cur1 : cur2;

        // 这里没有释放哨兵位头结点的内存，笔试和面试的时候建议
        // 先把结果保存起来，将 head 的内存释放掉，再返回结果
        return head->next; 
    }
};

// 递归
class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(!l1) return l2;
        if(!l2) return l1;

        if(l1->val <= l2->val)
        {
            // 将链表 l1->next 和 l2 合并的结果链接到 l1->next 上
            l1->next = mergeTwoLists(l1->next, l2); 
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};